home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / cols.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-12-10  |  5.5 KB  |  275 lines  |  [TEXT/R*ch]
  1. #include "port.h"
  2. #include "sparse_int.h"
  3.  
  4.  
  5. /*
  6.  *  allocate a new col vector 
  7.  */
  8. sm_col *sm_col_alloc(void)
  9. {
  10.     register sm_col *pcol;
  11.  
  12. #ifdef FAST_AND_LOOSE
  13.     if (sm_col_freelist == NIL(sm_col)) {
  14.     pcol = ALLOC(sm_col, 1);
  15.     } else {
  16.     pcol = sm_col_freelist;
  17.     sm_col_freelist = pcol->next_col;
  18.     }
  19. #else
  20.     pcol = ALLOC(sm_col, 1);
  21. #endif
  22.  
  23.     pcol->col_num = 0;
  24.     pcol->length = 0;
  25.     pcol->first_row = pcol->last_row = NIL(sm_element);
  26.     pcol->next_col = pcol->prev_col = NIL(sm_col);
  27.     pcol->flag = 0;
  28.     pcol->user_word = NIL(char);        /* for our user ... */
  29.     return pcol;
  30. }
  31.  
  32.  
  33. /*
  34.  *  free a col vector -- for FAST_AND_LOOSE, this is real cheap for cols;
  35.  *  however, freeing a rowumn must still walk down the rowumn discarding
  36.  *  the elements one-by-one; that is the only use for the extra '-DCOLS'
  37.  *  compile flag ...
  38.  */
  39. void sm_col_free(register sm_col *pcol)
  40. {
  41. #if defined(FAST_AND_LOOSE) && ! defined(COLS)
  42.     if (pcol->first_row != NIL(sm_element)) {
  43.     /* Add the linked list of col items to the free list */
  44.     pcol->last_row->next_row = sm_element_freelist;
  45.     sm_element_freelist = pcol->first_row;
  46.     }
  47.  
  48.     /* Add the col to the free list of cols */
  49.     pcol->next_col = sm_col_freelist;
  50.     sm_col_freelist = pcol;
  51. #else
  52.     register sm_element *p, *pnext;
  53.  
  54.     for(p = pcol->first_row; p != 0; p = pnext) {
  55.     pnext = p->next_row;
  56.     sm_element_free(p);
  57.     }
  58.     FREE(pcol);
  59. #endif
  60. }
  61.  
  62.  
  63. /*
  64.  *  duplicate an existing col
  65.  */
  66. sm_col *sm_col_dup(register sm_col *pcol)
  67. {
  68.     register sm_col *pnew;
  69.     register sm_element *p;
  70.  
  71.     pnew = sm_col_alloc();
  72.     for(p = pcol->first_row; p != 0; p = p->next_row) {
  73.     (void) sm_col_insert(pnew, p->row_num);
  74.     }
  75.     return pnew;
  76. }
  77.  
  78.  
  79. /*
  80.  *  insert an element into a col vector 
  81.  */
  82. sm_element *sm_col_insert(register sm_col *pcol, register int row)
  83. {
  84.     register sm_element *test, *element;
  85.  
  86.     /* get a new item, save its address */
  87.     sm_element_alloc(element);
  88.     test = element;
  89.     sorted_insert(sm_element, pcol->first_row, pcol->last_row, pcol->length, 
  90.             next_row, prev_row, row_num, row, test);
  91.  
  92.     /* if item was not used, free it */
  93.     if (element != test) {
  94.     sm_element_free(element);
  95.     }
  96.  
  97.     /* either way, return the current new value */
  98.     return test;
  99. }
  100.  
  101.  
  102. /*
  103.  *  remove an element from a col vector 
  104.  */
  105. void sm_col_remove(register sm_col *pcol, register int row)
  106. {
  107.     register sm_element *p;
  108.  
  109.     for(p = pcol->first_row; p != 0 && p->row_num < row; p = p->next_row)
  110.     ;
  111.     if (p != 0 && p->row_num == row) {
  112.     dll_unlink(p, pcol->first_row, pcol->last_row, 
  113.                 next_row, prev_row, pcol->length);
  114.     sm_element_free(p);
  115.     }
  116. }
  117.  
  118.  
  119. /*
  120.  *  find an element (if it is in the col vector)
  121.  */
  122. sm_element *sm_col_find(sm_col *pcol, int row)
  123. {
  124.     register sm_element *p;
  125.  
  126.     for(p = pcol->first_row; p != 0 && p->row_num < row; p = p->next_row)
  127.     ;
  128.     if (p != 0 && p->row_num == row) {
  129.     return p;
  130.     } else {
  131.     return NIL(sm_element);
  132.     }
  133. }
  134.  
  135. /*
  136.  *  return 1 if col p2 contains col p1; 0 otherwise
  137.  */
  138. int sm_col_contains(sm_col *p1, sm_col *p2)
  139. {
  140.     register sm_element *q1, *q2;
  141.  
  142.     q1 = p1->first_row;
  143.     q2 = p2->first_row;
  144.     while (q1 != 0) {
  145.     if (q2 == 0 || q1->row_num < q2->row_num) {
  146.         return 0;
  147.     } else if (q1->row_num == q2->row_num) {
  148.         q1 = q1->next_row;
  149.         q2 = q2->next_row;
  150.     } else {
  151.         q2 = q2->next_row;
  152.     }
  153.     }
  154.     return 1;
  155. }
  156.  
  157.  
  158. /*
  159.  *  return 1 if col p1 and col p2 share an element in common
  160.  */
  161. int sm_col_intersects(sm_col *p1, sm_col *p2)
  162. {
  163.     register sm_element *q1, *q2;
  164.  
  165.     q1 = p1->first_row;
  166.     q2 = p2->first_row;
  167.     if (q1 == 0 || q2 == 0) return 0;
  168.     for(;;) {
  169.     if (q1->row_num < q2->row_num) {
  170.         if ((q1 = q1->next_row) == 0) {
  171.         return 0;
  172.         }
  173.     } else if (q1->row_num > q2->row_num) {
  174.         if ((q2 = q2->next_row) == 0) {
  175.         return 0;
  176.         }
  177.     } else {
  178.         return 1;
  179.     }
  180.     }
  181. }
  182.  
  183.  
  184. /*
  185.  *  compare two cols, lexical ordering
  186.  */
  187. int sm_col_compare(sm_col *p1, sm_col *p2)
  188. {
  189.     register sm_element *q1, *q2;
  190.  
  191.     q1 = p1->first_row;
  192.     q2 = p2->first_row;
  193.     while(q1 != 0 && q2 != 0) {
  194.     if (q1->row_num != q2->row_num) {
  195.         return q1->row_num - q2->row_num;
  196.     }
  197.     q1 = q1->next_row;
  198.     q2 = q2->next_row;
  199.     }
  200.  
  201.     if (q1 != 0) {
  202.     return 1;
  203.     } else if (q2 != 0) {
  204.     return -1;
  205.     } else {
  206.     return 0;
  207.     }
  208. }
  209.  
  210.  
  211. /*
  212.  *  return the intersection
  213.  */
  214. sm_col *sm_col_and(sm_col *p1, sm_col *p2)
  215. {
  216.     register sm_element *q1, *q2;
  217.     register sm_col *result;
  218.  
  219.     result = sm_col_alloc();
  220.     q1 = p1->first_row;
  221.     q2 = p2->first_row;
  222.     if (q1 == 0 || q2 == 0) return result;
  223.     for(;;) {
  224.     if (q1->row_num < q2->row_num) {
  225.         if ((q1 = q1->next_row) == 0) {
  226.         return result;
  227.         }
  228.     } else if (q1->row_num > q2->row_num) {
  229.         if ((q2 = q2->next_row) == 0) {
  230.         return result;
  231.         }
  232.     } else {
  233.         (void) sm_col_insert(result, q1->row_num);
  234.         if ((q1 = q1->next_row) == 0) {
  235.         return result;
  236.         }
  237.         if ((q2 = q2->next_row) == 0) {
  238.         return result;
  239.         }
  240.     }
  241.     }
  242. }
  243.  
  244. int sm_col_hash(sm_col *pcol, int modulus)
  245. {
  246.     register int sum;
  247.     register sm_element *p;
  248.  
  249.     sum = 0;
  250.     for(p = pcol->first_row; p != 0; p = p->next_row) {
  251.     sum = (sum*17 + p->row_num) % modulus;
  252.     }
  253.     return sum;
  254. }
  255.  
  256. /*
  257.  *  remove an element from a col vector (given a pointer to the element) 
  258.  */
  259. void sm_col_remove_element(register sm_col *pcol, register sm_element *p)
  260. {
  261.     dll_unlink(p, pcol->first_row, pcol->last_row, 
  262.             next_row, prev_row, pcol->length);
  263.     sm_element_free(p);
  264. }
  265.  
  266.  
  267. void sm_col_print(FILE *fp, sm_col *pcol)
  268. {
  269.     sm_element *p;
  270.  
  271.     for(p = pcol->first_row; p != 0; p = p->next_row) {
  272.     (void) fprintf(fp, " %d", p->row_num);
  273.     }
  274. }
  275.